package main

import (
	"container/list"
	"errors"
	"fmt"
)

type LRU struct {
	size      int                   //LRU的容量
	innerList *list.List            //Golang 内置的双链表，来表示基于最近访问时间排序的序列
	innerMap  map[int]*list.Element //存储 key-value的hashmap
}

// 在 innerList 中链表节点的数据结构
type entry struct {
	key   int
	value int
}

// 初始化
func NewLRU(size int) (*LRU, error) {
	if size <= 0 {
		return nil, errors.New("must provide a positive size")
	}
	c := &LRU{
		size:      size,
		innerList: list.New(),
		innerMap:  make(map[int]*list.Element),
	}
	return c, nil
}

// 从 map 中基于 key 获取元素的信息，如果不存在，就直接返回不存在
func (c *LRU) Get(key int) (int, bool) {
	if e, ok := c.innerMap[key]; ok {
		// 要保证 LRU 的链表始终按照最近访问时间排序，get 之后需要把当前 key 对应的链表节点移动到链表的最开始;
		// Golang 内置的双链表中只需要调用 MoveToFront 就可以实现这一逻辑。
		c.innerList.MoveToFront(e)
		return e.Value.(*entry).value, true
	}
	return -1, false
}

func (c *LRU) Put(key int, value int) (evicted bool) {
	if e, ok := c.innerMap[key]; ok {
		//如果 put 的元素在 LRU 中已经存在，首先根据 innerMap 找到链表中的节点，移动到最前，并修改其中的 value 值就可以了
		c.innerList.MoveToFront(e)
		e.Value.(*entry).value = value
		return false
	} else {
		// 如果 LRU 中不存在指定 key 对应的记录，就需要在链表开头插入该节点，并在容量不足的时候，淘汰一个最近最少使用的节点。
		e := &entry{key, value}
		ent := c.innerList.PushFront(e)
		c.innerMap[key] = ent
		if c.innerList.Len() > c.size {
			last := c.innerList.Back()
			// 由于链表已经是基于访问时间从近到远有序排列的了，所以直接删除链表尾部元素就行。
			c.innerList.Remove(last)
			delete(c.innerMap, last.Value.(*entry).key)
			return true
		}
		return false
	}
}

func main() {
	lru, err := NewLRU(3)
	if err != nil {
		fmt.Println("LRU初始化失败:", err)
	}
	fmt.Println(lru)

	lru.Put(10, 10)
	lru.Put(10, 20)
	fmt.Println(lru)

	v, _ := lru.Get(10)
	fmt.Println(v)

	lru.Put(11, 11)
	lru.Put(12, 12)
	lru.Put(13, 13)
	lru.Put(11, 14)
	fmt.Println(lru)
	fmt.Println(lru.innerList.Len())
	fmt.Println(lru.innerList.Front().Value.(*entry).key)
}
